// @algorithm @lc id=2108 lang=cpp 
// @title minimize-the-difference-between-target-and-chosen-elements


// #define print(...)
// @test([[1,2,3],[4,5,6],[7,8,9]],13)=0
// @test([[1],[2],[3]],100)=94
// @test([[1,2,9,8,7]],6)=1
#define USE_DP
#ifdef USE_DP
class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        const int m = (int)mat.size();
        const int n = mat[0].size();
        // dp[j] 表示任取当前行某个数，是否存在和为 j 的情况
        // dp[j] = dp[j-1] | dp[j-x]
        vector<int> dp = {1}; // 和初始化为0,故 dp[0] = true
        int maxSum = 0; // 到当前行所选元素最大和
        for(auto & ln : mat){ // 逐行状态转移
            auto maxElem = *max_element(ln.begin(), ln.end());
            vector<int> dp2(maxSum + maxElem + 1, 0);
            for(auto & elem : ln){
                for(int j=elem; j<=maxSum+elem; j++)
                    dp2[j] |= dp[j-elem];
            }
            maxSum += maxElem;
            dp = move(dp2);
        }
        print("dp=", dp, "\n")
        int minDiff = INT_MAX;
        for(int j=0; j<=maxSum; j++){
            if(!dp[j]) continue;
            minDiff = min(abs(target-j), minDiff);
            if(!minDiff) return 0;
        }
        return minDiff;
    }
};
#else // DFS // 超时
class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int ans = INT_MAX, sum = 0;
        const int n = (int)mat.size();
        bool solved = false;
        function<void(int)> dfs = [&](int row){
            if(row == n){
                ans = min(abs(sum-target), ans);
                solved = ans == 0;
                return;
            }
            for(auto &v : mat[row]){
                if(solved) break;
                sum+=v;
                dfs(row+1);
                sum-=v;
            }
        };
        dfs(0);
        return ans;
    } 
};
#endif